import numpy as np


# 建立三张散列表。graph 存储关系图；costs 存储各个节点的开销（开销是指从起点到该节点的最小的权重）；parents 存储各个节点的父节点是谁。
# 创建一个数组用来存储已经处理过的节点 processed.
# BFS查找两点之间的最短路径，解决的“段数”最少
# Dijkstra 狄克斯特拉算法解决的是总权重最小的路径，一般解决加权图中的最短路径问题
# 这个算法只适用于有向无环图，而且只能用于边权为正的图，不能用于负边权的图中
# 核心代码，算法实现
# 找到最小开销，并更新
# 也就是说，该函数的功能就是找出在未处理的节点中的最小节点

class Dijkstra:
    def __init__(self, M):
        self.parents = []  # 存上一个节点
        self.processed = []  # 存已经处理过的节点
        self.costs = []
        self.M = M

    def find_lowest_cost_node(self):
        # float("inf")   表示正向无穷，一般我们对与节点到终点的位置距离定义为正向无穷
        lowest_cost = float("inf")
        lowest_cost_node = None
        size = len(self.costs)
        for node in range(size):  # 遍历所有的节点
            cost = self.costs[node]
            # 如果当前的节点开销更低而且没有被处理过，那么更新这个节点的开销
            if cost < lowest_cost and node not in self.processed:
                lowest_cost = cost
                lowest_cost_node = node
        return lowest_cost_node

    # 生成从start节点出发到其他节点的最短路径
    def shortedPath(self, start=0):
        size = len(self.M)
        self.parents = [-1 for i in range(size)]  # 存上一个节点
        self.processed = []  # 存已经处理过的节点
        self.costs = [np.inf for i in range(size)]  # 从start到各节点最短距离
        # parents[start] = -1
        # processed.append(start)
        self.costs[start] = 0

        # 开始结算
        node = self.find_lowest_cost_node()  # 在未处理的节点中，找出开销最小的节点
        while node is not None:
            cost = self.costs[node]
            neighbors = [i for i, n in enumerate(self.M[node]) if n != -1 and n != node]
            for n in neighbors:
                new_cost = cost + self.M[node][n]
                # 如果经历这个节点前往邻居更近，那么就更新邻居的开销，同时将邻居的父节点设为当前节点
                if self.costs[n] > new_cost:
                    self.costs[n] = new_cost
                    self.parents[n] = node
            # 将处理过的节点加入列表processed
            self.processed.append(node)
            # 找出下一个要处理的节点
            # print(costs)
            node = self.find_lowest_cost_node()

        return self.costs, self.parents
